"""
idea1:
simulate move action, double loop make it
"""


def func1(nums, k):
    for _ in range(k):
        tmp = nums[-1]  # 记录最后面的一个数字
        for i in range(len(nums) - 2, -1, -1):  # 从倒数第二个开始， nums[i+1]=nums[i]
            nums[i + 1] = nums[i]
        nums[0] = tmp  # 将记录的最后一个数字赋值到数组最前面
    return nums


assert func1([1, 2, 3, 4, 5, 6, 7, 8], 2) == [7, 8, 1, 2, 3, 4, 5, 6]

"""
idea2:
其实旋转数组k次，就是将k个尾部元素移动到了头部，同时将剩余元素向后移动。

那么将原始数组逆序，再对前k个元素逆序，即可得到旋转k次以后的数组了。
这种方式相当于对n个元素，每个元素被反转了2次，因此时间复杂度为O(n)，空间复杂度为O(1)

"""


def reverse(nums, start, end):
    while start < end:
        nums[start], nums[end] = nums[end], nums[start]
        start += 1
        end -= 1
    return nums


def func2(nums, k):
    k %= len(nums)
    reverse(nums, 0, len(nums) - 1)
    reverse(nums, 0, k - 1)
    reverse(nums, k, len(nums) - 1)
    return nums


print(func2([1, 2, 3, 4, 5, 6, 7, 8], 2))
